package tree;

import java.util.ArrayList;
import java.util.List;

// B树节点类
class BTreeNode {
    int[] keys;  // 存储键的数组
    int t;  // 阶
    BTreeNode[] children;  // 存储子节点的数组
    int n;  // 当前节点中的键的数量
    boolean leaf;  // 是否为叶子节点

    public BTreeNode(int t, boolean leaf) {
        this.t = t;
        this.leaf = leaf;
        this.keys = new int[2 * t - 1];
        this.children = new BTreeNode[2 * t];
        this.n = 0;
    }

    // 插入一个新的键
    public void insertNonFull(int key) {
        int i = n - 1;

        if (leaf) {
            // 如果是叶子节点，直接插入到合适的位置
            while (i >= 0 && keys[i] > key) {
                keys[i + 1] = keys[i];
                i--;
            }
            keys[i + 1] = key;
            n = n + 1;
        } else {
            // 如果不是叶子节点，找到应该插入的子节点
            while (i >= 0 && keys[i] > key) {
                i--;
            }
            i++;

            // 如果子节点已满，先分裂子节点
            if (children[i].n == 2 * t - 1) {
                splitChild(i, children[i]);

                // 分裂后判断需要插入到哪个子节点
                if (keys[i] < key) {
                    i++;
                }
            }
            children[i].insertNonFull(key);
        }
    }

    // 分裂子节点
    public void splitChild(int i, BTreeNode y) {
        // 创建一个新的节点 z，它将存储 y 的后半部分的键
        BTreeNode z = new BTreeNode(y.t, y.leaf);
        z.n = t - 1;

        // 将 y 的后半部分键复制到 z
        for (int j = 0; j < t - 1; j++) {
            z.keys[j] = y.keys[j + t];
        }

        // 如果 y 不是叶子节点，也要复制对应的子节点
        if (!y.leaf) {
            for (int j = 0; j < t; j++) {
                z.children[j] = y.children[j + t];
            }
        }

        // 减少 y 中的键数
        y.n = t - 1;

        // 将 z 作为 y 的父节点的一个新子节点
        for (int j = n; j >= i + 1; j--) {
            children[j + 1] = children[j];
        }

        children[i + 1] = z;

        // 移动当前节点的键以给新键腾出位置
        for (int j = n - 1; j >= i; j--) {
            keys[j + 1] = keys[j];
        }

        // 将 y 的中间键移到父节点中
        keys[i] = y.keys[t - 1];
        n = n + 1;
    }

    // 搜索键
    public BTreeNode search(int key) {
        int i = 0;
        // 找到第一个大于或等于 key 的键
        while (i < n && key > keys[i]) {
            i++;
        }

        // 如果找到则返回当前节点
        if (i < n && keys[i] == key) {
            return this;
        }

        // 如果是叶子节点且没有找到，则返回 null
        if (leaf) {
            return null;
        }

        // 否则继续在对应的子节点中搜索
        return children[i].search(key);
    }

    // 遍历节点
    public void traverse() {
        int i;
        for (i = 0; i < n; i++) {
            // 如果不是叶子节点，先遍历该键左边的子树
            if (!leaf) {
                children[i].traverse();
            }
            // 输出当前键
            System.out.print(keys[i] + " ");
        }

        // 最后遍历右边的子树
        if (!leaf) {
            children[i].traverse();
        }
    }
}

// B树类
public class BTree {
    BTreeNode root; // 树的根节点
    int t; // 阶

    public BTree(int t) {
        this.root = null;
        this.t = t;
    }

    // 遍历树
    public void traverse() {
        if (root != null) {
            root.traverse();
        }
    }

    // 搜索键
    public BTreeNode search(int key) {
        return (root == null) ? null : root.search(key);
    }

    // 插入一个键
    public void insert(int key) {
        if (root == null) {
            // 如果树为空，创建根节点
            root = new BTreeNode(t, true);
            root.keys[0] = key; // 插入键
            root.n = 1; // 更新根节点的键数量
        } else {
            // 如果根节点已满，树要增长高度
            if (root.n == 2 * t - 1) {
                BTreeNode s = new BTreeNode(t, false);
                s.children[0] = root;
                s.splitChild(0, root);

                // 判断插入到哪个子节点
                int i = 0;
                if (s.keys[0] < key) {
                    i++;
                }
                s.children[i].insertNonFull(key);

                // 更新根节点
                root = s;
            } else {
                root.insertNonFull(key);
            }
        }
    }

    public static void main(String[] args) {
        BTree tree = new BTree(3);  // 创建一个阶为3的B树

        // 插入一些键
        tree.insert(10);
        tree.insert(20);
        tree.insert(5);
        tree.insert(6);
        tree.insert(12);
        tree.insert(30);
        tree.insert(7);
        tree.insert(17);

        System.out.println("构建的B树的遍历结果：");
        tree.traverse();

        // 搜索键6是否存在
        int key = 6;
        if (tree.search(key) != null) {
            System.out.println("\n键 " + key + " 存在于B树中");
        } else {
            System.out.println("\n键 " + key + " 不存在于B树中");
        }
    }
}
